#include <vector>

using namespace std;

class Solution {
public:

    //搜索旋转排序数组
    int search(vector<int>& nums, int target) {
        int size = nums.size();
        if (nums.size()<=1 && nums[0]!=target)
        {
            return -1;
        }

        int left = 0;
        int right = size-1;

        while (left <= right)
        {
            int mid = (left + right) >> 1;
            if (nums[mid] == target)
            {
                return mid;
            }

            //判断左边有序
            if (nums[0] <= nums[mid])
            {
                if (nums[0] <= target && target < nums[mid])
                {
                    right = mid - 1;
                }
                else 
                {
                    left = mid + 1;
                }
            }
            else
            {
                if (nums[mid] < target && target <= nums[size-1])
                {
                    left = mid + 1;
                }
                else 
                {
                    right = mid - 1;
                }
            }
        }
        return -1;
    }


    //二进制链表转整数
    struct ListNode {
        int val;
        ListNode *next;
        ListNode() : val(0), next(nullptr) {}
        ListNode(int x) : val(x), next(nullptr) {}
        ListNode(int x, ListNode *next) : val(x), next(next) {}
    };

    //法一
    // int getDecimalValue(ListNode* head) {
    //     ListNode* rev = nullptr;
    //     ListNode* cur = head;

    //     while (cur != nullptr)
    //     {
    //         ListNode* next = cur->next;
    //         cur->next = rev;
    //         rev = cur;
    //         cur = next;
    //     }

    //     int ans = 0;
    //     for (size_t i = 0; rev != nullptr; ++i, rev = rev->next)
    //     {
    //         ans |= rev->val << i;
    //     }
    //     return ans;
    // }

    //法二
    int getDecimalValue(ListNode* head) {
        int ans = 0;
        ListNode* cur = head;
        while (cur != nullptr)
        {
            ans = ans * 2 + cur->val;
            cur = cur->next;
        }
        return ans;
    }
};
